function lengthOfLIS1(nums) {
  let len = nums.length;
  if (!len) return 0;
  let res = [nums[0]];
  for (let i = 1; i < len; i++) {
    let lastNums = res[res.length - 1];
    if (nums[i] > lastNums) {
      res.push(nums[i]);
    } else {
      let left = 0;
      let right = res.length - 1;
      while (left < right) {
        let min = (left + right) >> 1;
        if (nums[min] < nums[i]) {
          left = min + 1;
        } else {
          right = min;
        }
      }
      res[left] = nums[i];
    }
  }

  return res.length;
}

function lengthOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let dp = Array(len).fill(1);
  for (let i = 1; i < len; i++) {
    let cur = nums[i];
    for (let j = 0; j < i; j++) {
      if (cur > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

function indexOfLIS1(nums) {
  let len = nums.length;
  if (!len) return 0;
  let indexRes = [0];
  for (let i = 1; i < len; i++) {
    let lastCur = nums[indexRes[indexRes.length - 1]];
    if (nums[i] > lastCur) {
      indexRes.push(i);
    } else {
      let left = 0;
      let right = indexRes.length - 1;
      while (left < right) {
        let mid = (left + right) >> 1;
        if (nums[indexRes[mid]] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      indexRes[left] = i;
    }
  }
  return indexRes;
}

function indexOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let indexRes = [0];
  let prevIndex = [undefined]; // 用一个数组缓存前驱节点
  for (let i = 1; i < len; i++) {
    let lastCur = nums[indexRes[indexRes.length - 1]];
    if (nums[i] > lastCur) {
      // 能直接推 表示后面大于前面，直接保存前驱节点
      prevIndex[i] = indexRes[indexRes.length - 1];
      indexRes.push(i);
    } else {
      let left = 0;
      let right = indexRes.length - 1;
      while (left < right) {
        let mid = (left + right) >> 1;
        if (nums[indexRes[mid]] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      indexRes[left] = i;

      // 不能直接推 得判断替换的位置
      // 如果是首位，前驱节点为undefined，不是首位保存前驱节点
      if (left === 0) {
        prevIndex[i] = undefined;
      } else {
        prevIndex[i] = indexRes[left - 1];
      }
    }
  }

  let LISLength = indexRes.length;
  let index = indexRes[LISLength - 1];
  // 重后完前依次回溯修正正确的index
  while (LISLength > 0) {
    LISLength--;
    indexRes[LISLength] = index;
    index = prevIndex[index]; // 更新前驱节点
  }

  return indexRes;
}

/** test */

function lengthOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let dp = Array(len).fill(1);
  for (let i = 1; i < nums.length; i++) {
    let cur = nums[i];
    for (let j = 0; j < i; j++) {
      if (cur > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

function maxArr(nums) {
  let dp = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i], dp[i - 1] + nums[i]);
  }
  return Math.max(...dp);
}

function lengthOfLIS(nums) {
  let len = nums.length;
  if (!len) return 0;
  let res = [nums[0]];
  for (let i = 1; i < len; i++) {
    let lastItem = res[res.length - 1];
    if (nums[i] > lastItem) {
      res.push(nums[i]);
    } else {
      let left = 0;
      let right = res.length - 1;
      while (left < right) {
        let mid = (left + right) >> 1;
        if (res[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      res[left] = nums[i];
    }
  }
  return res.length;
}

export { lengthOfLIS, indexOfLIS };
